\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage[backend=bibtex,style=numeric]{biblatex}

\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

\addbibresource{citation.bib}

\begin{document}
	% =================================================
	\title{Numerical Analysis homework}
	
	\author{LiangYue 3220100159
		\thanks{Electronic address: \texttt{3220100159@zju.edu.cn}}}
	\affil{(Information and Computing Science 2201), Zhejiang University }
	
	
	\date{Due time: \today}
	
	\maketitle
	
	\begin{abstract}
	%	The abstract is not necessary for the theoretical homework, 
%		but for the programming project, 
	%	you are encouraged to write one.      
	\end{abstract}
	
	
	
	
	% ============================================
	\section*{I.Consider the bisection method starting with the initial interval [1.5,3.5].}
	
	\subsection*{I-a.What is the width of the interval at the nth step?}
	
	The initial width of interval is \[3.5-1.5=2\] 
	After the first loop,the the width has been changed to
	be half of the initial width.It happens each cycle.
	So at the nth step,the width of the interval is\[\left(\frac{1}{2}\right)^{(n-1)}\]

	
	\subsection*{I-b What is the supremum of the distance between the root r and the midpoint of the interval?}
	
	By I-a,we know that the width of the interval at the nth step is \[\left(\frac{1}{2}\right)^{(n-1)}\] So the distance between the root r and the midpoint of the interval must be no greater than half of the width of the interval at the nth step,which means \[\left(\frac{1}{2}\right)^{n}\]
	
	\section*{II.In using the bisection algorithm with its initial interval as $[a_0,b_0]$ with $a_0$ >0,we want to determine the root with its relative error no greater than $\epsilon$.Prove that this goal of accuracy is guaranteed by the following choice of the number of steps,
		\[n{\ge}\frac{\log_{}{(b_0-a_0)}-\log_{}{\epsilon}-\log_{}{a_0}}{\log_{}{2}}-1\]}
		
	By I,we know the supremum of the distance between the root r and the midpoint of the interval is \[|\frac{b_0-a_0}{2^{n+1}}|\]
	Let $r_n$ be the midpoint of the nth interval,so we have
	\[\frac{|r_n-r|}{|r|}{\le}\frac{|b_0-a_0|}{|2^{n+1}a_0|}\]
	and it is no greater than $\epsilon$.So take the logarithm base 2 on both sides,then \[\log_{2}{\epsilon}{\ge}\log_{2}{|b_0-a_0|}-\log_{2}{2^{n+1}}-\log_{2}{a_0}\]	\[(a_0>0,b_0>a_0)\]
	By \[\log_{a}{b}=\frac{\log_{c}{b}}{\log_{c}{a}}\]

	we have	\[n{\ge}\frac{\log_{}{(b_0-a_0)}-\log_{}{\epsilon}-\log_{}{a_0}}{\log_{}{2}}-1\]

	\section*{III.Perform four iterations of Newton's method for the polynomial equation $p(x)=4x^{3}-2x^{2}+3$ with the starting point $x_0=-1$.Use a hand calculator and organize results of the iterations in a table.}
	
	Starting point $x_0=-1$.
	Newton iteration:\[x_{n+1}=x_n-\frac{p(x_n)}{p^{'}(x_n)}\]
	And we know easily that$p^{'}(x)=12x^{2}-4x$.
	So for the starting point \( x_0 \), we have\[ p'(x_0) = 16, \quad p(x_0) = -3 \]
	So \[ x_1 = x_0 - \frac{p(x_0)}{p'(x_0)} = -1 - \frac{-3}{16} = -\frac{13}{16} \]
	Then we can get the value of $x_2$,$x_3$ and $x_4$ by the same way.
	\[x_2=-\frac{4409}{5720}\]
	\[x_3=-\frac{183686929759}{238916743780}\]
	\[x_4=-\frac{6663598643755300672108676539985512}{8667215423352044128081221499038535}\]
	
	\section*{IV. Consider a variation of Newton's method in which only the derivative at \( x_0 \) is used,\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_0)}\].Find \( C \) and \( s \) such that\[e_{n+1} = C e_n^s\] where \( e_n \) is the error of Newton's method at step \( n \), \( s \) is a constant, and \( C \) may depend on \( x_n \), the true solution \( \alpha \), and the derivative of the function \( f \).}
	First of all,we know 
	\[e_{n}=x_n-\alpha\]        (1)
	\[e_{n+1}=x_{n+1}-\alpha\]  (2) 
	\paragraph{Where \( \alpha \) is the true root of \( f(x) \).}
	Perform a Taylor expansion of \( f \) around \( x_n \):
	\[f(x_n) = f(\alpha) + f'(\alpha)(x_n - \alpha) + \frac{1}{2} f''(\alpha)(x_n - \alpha)^2 + \ldots\]
	Substitute \( f(x_n) \) into the iterative formula, then we have:
	\[x_{n+1} = x_n - \frac{f'(\alpha)(x_n - \alpha) + \frac{1}{2} f''(\alpha)(x_n - \alpha)^2}{f'(x_0)}\]
	Ignore the higher-order terms, we have:
	\[x_{n+1} = \alpha +\frac{f'(\alpha)-f'(x_0)}{f'(x_0)}(x_n - \alpha)\]
	Then with (1) and (2) we get:
	\[e_{n+1} = e_n \frac{f'(\alpha) - f'(x_0)}{f'(x_0)}\]
	So \\
	\( C = \frac{f'(\alpha) - f'(x_0)}{f'(x_0)} \), which
	depends on \( x_0 \), \( \alpha \), and the derivative of
	\( f \);\\
	\( s = 1 \).
	
	\section*{V. Within (\(-\frac{\pi}{2},\frac{\pi}{2}\)), will the iteration \(x_{n+1} = \arctan(x_n)\) converge?}
	
	For \(x_{n+1} = \arctan(x_n)\),it is strictly increasing and bounded.So it satisfies the condition of a contraction mapping.And it will converges to a fixed point.\\
	\\
	To find the fixed point,we have that fixed point satisfies:
	\(x=\arctan(x)\).\\
	\\
	Solving the equation,we find when \(x=0,x=\arctan(x)\).\\
	\\
	Moreover, the derivative of \(\arctan(x)\) is \(\frac{1}{(1+x^{2})}\) which is no greater than 1.So there exists k,(0<k<1) such that \(|\arctan(x)-\arctan(y)| \le k|x-y|\) ,for any x,y.\\
	\\
	\\
	So the iteration will converge to its fixed point $x=0$.
	
	\section*{VI.Let p$>$1.What is the value of the following continued fraction?\[x=\frac{1}{p+\frac{1}{p+\frac{1}{p+...}}}\]
	Prove that the sequence of values converges.(Hint:this can be interpreted as \(x=\lim_{n\to \infty} x_n\),where $x_1$=$\frac{1}{p}$,$x_2$=$\frac{1}{1+\frac{1}{p}}$,$x_3$=$\frac{1}{p+\frac{1}{p+\frac{1}{p}}}$,...,and so forth.Formulate x as a fixed point of some function.)}
	
	Interpreting the sequence as \(x=\lim_{n\to \infty}x_n\),\\
	And we have\\
	$x_1$=$\frac{1}{p}$,\\
	$x_2$=$\frac{1}{1+\frac{1}{p}}$,\\
	$x_3$=$\frac{1}{p+\frac{1}{p+\frac{1}{p}}}$,...\\
	By observation, we find (1) \[x_{n+1}=\frac{1}{p+x_n}\]    
	We assume that the sequence will converge to x,which means\[x=\frac{1}{p+x}\]Solving the equation ,we have \(x=\frac{-p+(p^{2}+4)^{\frac{1}{2}}}{2}\)(for x$>$0,we rule \(x=\frac{-p-(p^{2}+4)^{\frac{1}{2}}}{2}\)out)\\
	So we find the fixed point now.\\
	Let us verify the convergence. \\
	By (1),
	\(x_{n+1}-x_n=\frac{1}{p+x_n}-x_n\),($x_n$$>$0,for all n) which is always no greater than 0 for p$>$1.
	So the sequence is strictly decreasing.\\
	Moreover it is bounded by 0.\\
	By Monotone Convergence Theorem,the sequence converges to \(\frac{-p+(p^{2}+4)^{\frac{1}{2}}}{2}\).
	
	\section*{VII.What happens in the problem II if $a_0 < 0 < b_0$?Derive an inequality of the number of steps similar to that in II.In this case, is the relative error still an appropriate measure?}
	Assume $\alpha$ is the true root.\\
	If $a_0 < 0 < b_0$, there exists the probability that $\alpha$ is very close to 0.So $|\alpha|$ is also very close to 0,which will lead to the value of $|\frac{r_n-\alpha}{\alpha}|$ (the relative error) can't reflect the amount of error.\\
	So the absolute error is better than the relative error here.\\
	So
	\[\frac{b_0-a_0}{2^{n+1}} < \epsilon\]
	\[n > \frac{\log_{}{(b_0-a_0)}-\log_{}{\epsilon}}{\log_{}{2}}-1\].
	
	\section*{VIII.Consider solving f(x) = 0 ($f \in \mathcal{C}^{k+1})$ by Newton's method with the starting point close to a root of multiplicity k.Note that $\alpha$ is a zero of multiplicity k of the function f if\[f^{(k)}(\alpha)\ne0;     \forall i < k, f^{(i)}(\alpha)=0. \]}
	\subsection*{VIII-a.How can a multiple zero be detected by examining the behavior of the points ($x_n,f(x_n)$)?}
	If r is a multiple zero of f, it satisfies:
	\(f(x)=(x-r)^{m}h(x)\),where h(x)$\ne$0.So \\
	\[f^{'}(x)=m(x-r)^{m-1}(h(x))+h^{'}(x)(x-r)^{m}\]
	where $f^{'}(r)=0$.
	And so on,we have:
	\[f^{(k)}(r) \ne 0 ;  \forall i < m, f^{(i)}(r)=0. \]
	So if $x_n$ satisfies the condition above, or $f^{i}(x_n)$ very close to zero($0 < i < m$), we can guess that there may exist a zero of multiplicity m.In other words,if $f(x_n)$ changes very slowly, there may exist a zero of multiplicity m.
	
	\subsection*{VIII-b.Prove that if r is a zero of multiplicity k of the function f,then quadratic convergence in Newton's iteration will be restored by making this modification:\[x_{n+1}=x_n-k\frac{f(x_n)}{f^{'}(x_n)}.\]}
	r satisfies:\\
	\[f^{(k)}(r) \ne 0 ;     \forall i < k, f^{(i)}(r)=0. \]
	And \(f(x)=(x-r)^{k}h(x)\), where h(x)$\ne$0.\\
	Then,\[f(x)^{\frac{1}{k}}=(x-r)h(x)^{\frac{1}{k}}.\]
	So r is the zero of \(f(x)^{\frac{1}{k}}=0\).\\
	Applying the Newton's method:
	\[x_{n+1}=x_n-\frac{f(x_n)^{\frac{1}{k}}}{\frac{f(x_n)^{\frac{1}{k}-1}f^{'}(x_n)}{k}}\]
	i.e.\[x_{n+1}=x_n-k\frac{f(x_n)}{f^{'}(x_n)} ,m=0,1,2,...\]

	
	
	
	% ===============================================
	\section*{ \center{\normalsize {Acknowledgement}} }
	Give your acknowledgements here(if any).
	
	
	\printbibliography
	
	If you are not familiar with \texttt{bibtex}, 
	it is acceptable to put a table here for your references.
\end{document}